Convolutional codes are a class of channel codes used to mitigate the effects of channel noise in the transmission of information. As is well known, the convolutional encoder in a transmitter is a finite-state machine whose operation may be described in terms of a trellis. As it accepts data bits, the convolutional encoder proceeds through a sequence of states and produces an output which subsequently is used to define an output sequence of symbols that is transmitted over a (noisy or otherwise impaired) channel. The output sequence of symbols corresponds to a path though the trellis that describes the encoder operation.
In the receiver, a maximum likelihood decoder for convolutional codes, known in the art as the Viterbi decoder, determines the output sequence of symbols that was transmitted based on the received corrupted version of the transmitted sequence of symbols and knowledge of the code used by the encoder. The output sequence corresponds to the "best path", which is typically the single path through the trellis having the best so-called path metric. For the Gaussian channel, for example, the determination of the output sequence is made by correlating with the received version all possible transmitted sequences (corresponding to paths through the trellis) and then choosing, as the "maximum likelihood" sequence, the sequence where the correlation is maximum.
As it operates, the Viterbi decoder disregards a number of paths in the trellis and considers only the so-called surviving paths as candidates for the best path. Looking backwards in the trellis over time, the surviving paths tend to merge into the same predecessor path. The so-called path memory is the length of the sequence of symbols in each path (or correspondingly, the length of the paths) that the Viterbi decoder must "remember" before making a decoding decision.
There are several ways in which the decoding decisions may be made or "released". For example, the decoder may make its decision on the best path after it processes the entire received sequence of symbols. That is, after the decoder completes its forward pass through the trellis, the best path is identified and the sequence of symbols associated with the best path is released as the maximum likelihood sequence. In this case, path memory typically corresponds to the length of the received sequence or best path.
Alternatively, for example where the received sequence is very long, the decoder makes its decision as to the value of the received symbol sequence on a symbol. by-symbol basis. This method is referred to as continuous Viterbi decoding. In this case, path memory is said to be truncated to a special length--that is, path memory has a value less than that which would be used in the above-described case--and is referred to as a "decoding window". As the decoder receives a symbol(s), new surviving paths having updated path metrics are identified. A decision is made as to the value of the earliest received symbol(s) within the decoding window by tracing back along one of the surviving paths, typically the path identified as the best path at that time. The decoding window is said to slide forward and the process is repeated. Typically, the decoding window is chosen to be at least "long enough" that it is highly probable that the surviving paths merge within it.
Also known in the art is a group of extended Viterbi algorithms referred to as the List Viterbi algorithms. Whereas the Viterbi algorithm described above (hereinafter referred to as the "regular" Viterbi algorithm) identifies the single best path through the trellis, a List Viterbi algorithm identifies the L best paths, or L best candidates, though the trellis. (The case in which L=1 is the regular Viterbi algorithm.) Versions of the List Viterbi algorithms produce a rank ordered list of the L best candidate decodings corresponding to a block of convolutional coded data. See, for example, U.S. Pat. No. 5,208,816, issued May 4, 1993 to Seshadri and Sundberg, and U.S. Pat. No. 5,537,444, issued Jul. 16, 1996 to Nill and Sundberg. List Viterbi algorithms have been found to be advantageous for error detection/correction for convolutionally encoded data and, in particular, have been found to be effective in reducing error flag rates for digital audio broadcasting applications.
List Viterbi algorithms known in the art were designed for block-by-block transmission and execute with a path memory extending from a starting state to a terminating state, hereinafter referred to as an LVA starting and an LVA terminating state, respectively. The List Viterbi algorithms require that the decoder know the identities of the LVA starting and terminating states. In the prior art, in order to find the L best candidates corresponding to a data block, the LVA starting state is the block starting state, i.e., the state of the encoder when the block encoding commenced, and the LVA terminating state is the block terminating state, i.e., the encoder state when the block encoding terminated. Thus, the decoder is required to know the block starting and block terminating states.
Providing the decoder with knowledge of a block starting state is easy to achieve. However, providing the decoder with knowledge of a block terminating state is not so straightforward and typically requires that the block of data be terminated with a number of additional known bits, referred to as a tail. Such data is said to have been "blockwise terminated" with a tail. Disadvantageously, however, the tail represents overhead, for example in terms of wasted bandwidth.
It is desirable to be able to obtain the advantages of using a List Viterbi algorithm to decode blocks of information, without incurring the overhead of a tail. In prior investigations by one of us, it was speculated that a prior art List Viterbi algorithm may be modified to operate in such a mode by utilizing continuous Viterbi decoding--that is, the sliding decoding window approach discussed above. Specifically, it was conjectured that, using this approach, the L best surviving paths into each state could be maintained and at each instant the L best symbols would be released by tracing back D symbols, where D is the so-called decoding depth, along the L best surviving paths. The decoding depth is the depth looking backwards within the trellis at which it is highly probable that the surviving paths will merge. See, for example, "List Viterbi Decoding Algorithms with Applications", by Seshadri and Sundberg, IEEE Transactions on Communications, Vol. 42, February/March/April 1994, p. 313-23.
We, however, have now realized that the sliding decoding window approach will not produce the list of the L best candidates over a block, even if the length of the decoding window is greater than the block length, due, in part, to the fact that the surviving paths will likely merge over the decoding depth. There has thus remained in the art the problem of how to implement a List Viterbi algorithm in the decoding of blocks or frames of information which have not been terminated with a tail.